package test_9;

/**
 * Created by xiebang
 * Description
 * User:小谢
 * Date:2021-11-25
 * Time:17:27
 */
public class TestDemo {


    public class Solution {
        /**
         * @param S string字符串
         * @param T string字符串
         * @return int整型
         */
        public int numDistinct(String S, String T) {
            // write code here
            int row = S.length();
            int col = T.length();

            int[][] count = new int[row + 1][col + 1];

            //初始值
            for (int i = 0; i <= row; i++) {
                count[i][0] = 1;
            }
            for (int i = 1; i <= col; i++) {
                count[0][i] = 0;
            }

            for (int i = 1; i <= row; i++) {
                for (int j = 1; j <= col; j++) {
                    if (S.charAt(i - 1) == T.charAt(j - 1)) {
                        count[i][j] = count[i - 1][j - 1] + count[i - 1][j];
                    } else {
                        count[i][j] = count[i - 1][j];
                    }
                }

            }
            return count[row][col];

        }
    }
}